#include <cstdio>
#include <queue>
using namespace std;

#define INF 1000000000

struct Node
{
    int x, y, t;
    Node( ) { }
    Node( int _x, int _y, int _t )
        : x( _x ), y( _y ), t( _t ) { }
};

bool operator < ( const Node &a, const Node &b )
{
    return a.t > b.t;
}

int dir[][ 2 ] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
int n, m, sx, sy, d[ 501 ][ 501 ], v;
char map[ 501 ][ 501 ];
priority_queue<Node> q;

void init( )
{
    int i, j;
    scanf("%d%d%d", &n, &m, &v);
    for ( i = 0; i < n; i++ )
    {
        scanf("%s", map[ i ]);
        for ( j = 0; j < m; j++ )
        {
            if ( map[ i ][ j ] == 'S' )
            {
                sx = i;
                sy = j;
            }
            d[ i ][ j ] = INF;
        }
    }
    d[ sx ][ sy ] = 0;
    while ( !q.empty( ) ) q.pop( );
    q.push( Node( sx, sy, 0 ) );
}

void work( )
{
    Node p;
    int i;
    while ( !q.empty( ) )
    {
        p = q.top( );
        q.pop( );
        if ( p.x == 0 || p.x == n - 1 || p.y == 0 || p.y == m - 1 ) break;
        if ( p.t > d[ p.x ][ p.y ] ) continue;
        for ( i = 0; i < 4; i++ )
        {
            if ( map[ p.x + dir[ i ][ 0 ] ][ p.y + dir[ i ][ 1 ] ] == '.' )
                if ( d[ p.x + dir[ i ][ 0 ] ][ p.y + dir[ i ][ 1 ] ] > p.t + 1 )
                {
                    d[ p.x + dir[ i ][ 0 ] ][ p.y + dir[ i ][ 1 ] ] = p.t + 1;
                    q.push( Node( p.x + dir[ i ][ 0 ], p.y + dir[ i ][ 1 ], p.t + 1 ) );
                }
            if ( map[ p.x + dir[ i ][ 0 ] ][ p.y + dir[ i ][ 1 ] ] == '@' )
                if ( d[ p.x + dir[ i ][ 0 ] ][ p.y + dir[ i ][ 1 ] ] > p.t + 1 + v )
                {
                    d[ p.x + dir[ i ][ 0 ] ][ p.y + dir[ i ][ 1 ] ] = p.t + 1 + v;
                    q.push( Node( p.x + dir[ i ][ 0 ], p.y + dir[ i ][ 1 ], p.t + 1 + v ) );
                }
        }
    }
    printf("%d\n", p.t + 1);
}

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        init( );
        work( );
    }
    return 0;
}
